import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        //求第n项的斐波那契数
        long ret = fib1(5);
        long ret2 = fib2(5);
        System.out.println(ret);
        System.out.println(ret2);
    }
    public static long fib2(int n) {
        if(n==1) {
            return 0;
        }
        if(n==2) {
            return 1;
        }
        int f1 = 0;
        int f2 = 1;
        int f3 = -1;//为了防止上面的判断忘写
        for(int i=3;i<=n;i++) {
            f3 = f2 + f1;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }



    public static long fib1(int n) {
        if(n==1) {
            return 0;
        }
        if(n==2) {
            return 1;
        }
        return fib1(n-1)+fib1(n-2);
    }



    public static void main3(String[] args) {
        //输入1279  返回1+7+2+9
        int ret = sum(1279);
        System.out.println(ret);
    }
    public static int sum(int num) {
        if(num<=9) {
            return num;
        }
        return num%10+sum(num/10);
    }

    public static void main2(String[] args) {
        //递归
        print(123);
    }
    public static void print(int num) {
        if(num<=9) {
            System.out.print(num+" ");
            return;
        }
        print(num/10);
        System.out.print(num%10+" ");
    }


    public static void main1(String[] args) {
        //二分查找
        int[] array = new int[]{1,3,6,9,12,56,98};
        int k=9;
        int left=0;
        int right=array.length-1;
        binarySearch(array,k,left,right);
    }
    public static void binarySearch(int[] array,int val,int left,int right) {
        if(array==null) {
            System.out.println("数组为空！");
        }
        while(left<=right) {
            int mid=left+(right-left)/2;
            if(array[mid]>val) {
                left=mid+1;
            }
            else if (array[mid]<val) {
                right=mid-1;
            }
            else {
                System.out.println("找到的元素下标是：" + mid);
                break;
            }
        }
        if (left > right) {
            System.out.println("Element is not found!");
        }
    }
}
